/**
 * @file bloom_filter_test.cpp
 *
 * Copyright (C) Metaswitch Networks 2017
 * If license terms are provided to you in a COPYING file in the root directory
 * of the source code repository by which you are accessing this code, then
 * the license outlined in that COPYING file applies to your use.
 * Otherwise no rights are granted except for those provided to you by
 * Metaswitch Networks in a separate written agreement.
 */

#include "gmock/gmock.h"
#include "gtest/gtest.h"

#include "bloom_filter.h"

using ::testing::Return;
using ::testing::_;

//
// Bloom filter tests.
//
// Bloom filters are probabilistic data structures that can return incorrect
// results (false positives), which means these tests can spuriously fail. There
// isn't a good way around this, but the failure rate should be ~0.01%, which is
// sufficiently low as not to be a problem.
//

TEST(BloomFilterTest, NewBloomFilterIsEmpty)
{
  BloomFilter bf(10000, 1);
  EXPECT_FALSE(bf.check("Kermit"));
  EXPECT_FALSE(bf.check("MissPiggy"));
  EXPECT_FALSE(bf.check("Gonzo"));
  EXPECT_FALSE(bf.check("Animal"));
}

TEST(BloomFilterTest, OneBitPerItem)
{
  BloomFilter bf(10000, 1);

  bf.add("Kermit");
  bf.add("MissPiggy");

  EXPECT_TRUE(bf.check("Kermit"));
  EXPECT_TRUE(bf.check("MissPiggy"));
  EXPECT_FALSE(bf.check("Gonzo"));
  EXPECT_FALSE(bf.check("Animal"));
}

TEST(BloomFilterTest, TwoBitsPerItem)
{
  BloomFilter bf(10000, 2);

  bf.add("Kermit");
  bf.add("MissPiggy");

  EXPECT_TRUE(bf.check("Kermit"));
  EXPECT_TRUE(bf.check("MissPiggy"));
  EXPECT_FALSE(bf.check("Gonzo"));
  EXPECT_FALSE(bf.check("Animal"));
}

TEST(BloomFilterTest, ManyBitsPerItem)
{
  BloomFilter bf(100000, 10);

  bf.add("Kermit");
  bf.add("MissPiggy");

  EXPECT_TRUE(bf.check("Kermit"));
  EXPECT_TRUE(bf.check("MissPiggy"));
  EXPECT_FALSE(bf.check("Gonzo"));
  EXPECT_FALSE(bf.check("Animal"));
}

TEST(BloomFilterTest, NumEntriesAndFalsePositiveRate)
{
  BloomFilter* bf = BloomFilter::for_num_entries_and_fp_prob(2, 0.0001);

  bf->add("Kermit");
  bf->add("MissPiggy");

  EXPECT_TRUE(bf->check("Kermit"));
  EXPECT_TRUE(bf->check("MissPiggy"));
  EXPECT_FALSE(bf->check("Gonzo"));
  EXPECT_FALSE(bf->check("Animal"));

  delete bf; bf = nullptr;
}

TEST(BloomFilterTest, BadConstructorArguments)
{
  EXPECT_EQ(BloomFilter::for_num_entries_and_fp_prob(0, 0.5), nullptr);
  EXPECT_EQ(BloomFilter::for_num_entries_and_fp_prob(1, -0.5), nullptr);
  EXPECT_EQ(BloomFilter::for_num_entries_and_fp_prob(1, 1.5), nullptr);
}

TEST(BloomFilterTest, JsonSerializeDeserialize)
{
  BloomFilter bf(100000, 10);

  bf.add("Kermit");
  bf.add("MissPiggy");

  // Serialize and deserialize the bloom filter.
  BloomFilter* bf2 = BloomFilter::from_json(bf.to_json());

  EXPECT_NE(bf2, nullptr);
  EXPECT_TRUE(bf2->check("Kermit"));
  EXPECT_TRUE(bf2->check("MissPiggy"));
  EXPECT_FALSE(bf2->check("Gonzo"));
  EXPECT_FALSE(bf2->check("Animal"));

  delete bf2; bf2 = nullptr;
}

TEST(BloomFilterTest, JsonSerializeDeserializeEmpty)
{
  BloomFilter bf(100000, 10);

  // Serialize and deserialize the bloom filter.
  BloomFilter* bf2 = BloomFilter::from_json(bf.to_json());

  EXPECT_NE(bf2, nullptr);
  EXPECT_FALSE(bf2->check("Kermit"));
  EXPECT_FALSE(bf2->check("MissPiggy"));
  EXPECT_FALSE(bf2->check("Gonzo"));
  EXPECT_FALSE(bf2->check("Animal"));

  delete bf2; bf2 = nullptr;
}

TEST(BloomFilterTest, JsonDeserialize3rdParty)
{
  // A bloom filter that conforms to the JSON API but was generated by an
  // independent 3rd party implementation. It contains the strings "Kermit" and
  // "MissPiggy".
  const std::string json =
    "{\"bitmap\":\"J+i5Mg==\",\"total_bits\":32,\"bits_per_entry\":12,"
     "\"hash0\":{\"k0\":6547054200929830170,\"k1\":9813628641652032020},"
     "\"hash1\":{\"k0\":15888472079188754020,\"k1\":14822504794822470401}}";

  BloomFilter* bf = BloomFilter::from_json(json);

  EXPECT_NE(bf, nullptr);
  EXPECT_TRUE(bf->check("Kermit"));
  EXPECT_TRUE(bf->check("MissPiggy"));
  EXPECT_FALSE(bf->check("Gonzo"));
  EXPECT_FALSE(bf->check("Animal"));

  delete bf; bf = nullptr;
}

TEST(BloomFilterTest, JsonDeserializeExtraFields)
{
  // A bloom filter that contains some additional fields that our implementation
  // does not recognize. This should be accepted, as it represents a
  // backwards-compatible change to the filter.
  const std::string json =
    "{\"bitmap\":\"J+i5Mg==\",\"total_bits\":32,\"bits_per_entry\":12,"
     "\"hash0\":{\"k0\":6547054200929830170,\"k1\":9813628641652032020},"
     "\"hash1\":{\"k0\":15888472079188754020,\"k1\":14822504794822470401},"
     "\"future\": \"unknown\"}";

  BloomFilter* bf = BloomFilter::from_json(json);

  EXPECT_NE(bf, nullptr);
  EXPECT_TRUE(bf->check("Kermit"));
  EXPECT_TRUE(bf->check("MissPiggy"));
  EXPECT_FALSE(bf->check("Gonzo"));
  EXPECT_FALSE(bf->check("Animal"));

  delete bf; bf = nullptr;
}

TEST(BloomFilterTest, BadJson)
{
  // A string that is not valid JSON.
  EXPECT_EQ(BloomFilter::from_json("It's the muppet show"), nullptr);

  // A string that is valid JSON but not a valid bloom filter.
  EXPECT_EQ(BloomFilter::from_json("{}"), nullptr);

  // A string that is not a valid bloom filter because the bitmap is not valid
  // base64.
  const std::string json =
    "{\"bitmap\":\"^^^^^^^\",\"total_bits\":32,\"bits_per_entry\":12,"
     "\"hash0\":{\"k0\":6547054200929830170,\"k1\":9813628641652032020},"
     "\"hash1\":{\"k0\":15888472079188754020,\"k1\":14822504794822470401}}";
  EXPECT_EQ(BloomFilter::from_json(json), nullptr);
}
